#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#if 0
#include "HashSet.h"
#else
#include <memory.h>

/* Hash set data structure. */
#define HashSet(Ty, MaxItems, NumBuckets) \
    struct { \
        struct { \
            Ty key;                 /* key of the item */           \
            unsigned next;          /* index to next node + 1 */    \
        } items[MaxItems];          /* array of nodes */            \
        unsigned num_items;         /* number of nodes */           \
        unsigned head[NumBuckets];  /* index to first node + 1 */   \
        unsigned (*hash)(Ty);       /* hash function */             \
        int (*compare)(Ty, Ty);     /* comparison function */       \
    }

/* Initializes a hash set. */
#define HashSet_init(Set, Hasher, Comparer)         \
    do {                                            \
        (Set).compare = (Comparer);                 \
        (Set).hash = (Hasher);                      \
        (Set).num_items = 0;                        \
        memset((Set).head, 0, sizeof((Set).head));  \
    } while (0)

/* Clears the elements in the hash set. */
#define HashSet_clear(Set)                          \
    do {                                            \
        memset((Set).head, 0, sizeof((Set).head));  \
        (Set).num_items = 0;                        \
    } while (0)

/* Returns the number of buckets in a hash set. */
#define HashSet_numBuckets(Set) (sizeof((Set).head)/sizeof((Set).head[0]))

/* Compares two keys using the hash set's comparison function. */
#define HashSet_compare(Set, Key1, Key2) \
    (((Set).compare)? (Set).compare((Key1),(Key2)) : (Key1)-(Key2))

/* Computes the hash value of a key using a hash set's hash function. */
#define HashSet_hash(Set, Key) \
    (((Set).hash)? (Set).hash((Key)) : (unsigned int)(Key))

/* Looks up the hash set for a given key. If the key is found, its one-based
 * index is stored in ReturnIndex; if the key is not found, 0 is stored.
 */
#define HashSet_find(Set, Key, ReturnIndex) \
    do { \
        unsigned code = HashSet_hash(Set, Key);                         \
        unsigned bucket = code % HashSet_numBuckets(Set);               \
        unsigned k;                                                     \
        for (k = (Set).head[bucket]; k; k = (Set).items[k-1].next)      \
            if (HashSet_compare(Set, Key, (Set).items[k-1].key) == 0)   \
                break;                                                  \
        (ReturnIndex) = k;                                              \
    } while (0)

/* Adds a key into a hash set. Returns the one-based index of the added key
 * in ReturnIndex. If the key already exists in the hash set, the effect is
 * the same as HashSet_find(Set, Key, ReturnIndex). Since the key is copied
 * by bytes into the hash set, it must be an l-value of the key type.
 */
#define HashSet_add(Set, Key, ReturnIndex) \
    do { \
        unsigned code = HashSet_hash(Set, Key);                         \
        unsigned bucket = code % HashSet_numBuckets(Set);               \
        unsigned k;                                                     \
        for (k = (Set).head[bucket]; k; k = (Set).items[k-1].next)      \
            if (HashSet_compare(Set, Key, (Set).items[k-1].key) == 0)   \
                break;                                                  \
        if (k == 0) {                                                   \
            k = ++(Set).num_items;                                      \
            (Set).items[k-1].next = (Set).head[bucket];                 \
            (Set).head[bucket] = k;                                     \
            memcpy(&(Set).items[k-1].key, &(Key),                       \
                   sizeof((Set).items[0].key));                         \
        }                                                               \
        (ReturnIndex) = k;                                              \
    } while (0)

/* Returns the number of elements in a hash set. */
#define HashSet_size(Set) ((Set).num_items)

/* Gets the item key at a given one-based index. */
#define HashSet_get(Set, Index) ((Set).items[(Index)-1].key)

/* Default string hash function. */
unsigned strhash(const char *s)
{
    unsigned power = 1;
    unsigned code = 0;
    for (; *s; s++)
    {
        code += (unsigned char)(*s) * power;
        power *= 31;
    }
    return code;
}
#endif

typedef struct component
{
    int type;       /* type id (0-based) */
    int price;      /* price of the component */
    int quality;    /* quality of the component */
    int upgrade;    /* index of the just-better component of the same type */
} component;

static int component_quality_comparer(const component *a, const component *b)
{
    return a->quality - b->quality;
}

#define MAX_PRICE       1000000
#define MAX_QUALITY     1000000000
#define MAX_COMPONENTS  1000
#define MAX_TYPES       1000

static component components[MAX_COMPONENTS+1];
static int num_components;
static int num_types;
static int budget;
typedef char TypeString[24];
static HashSet(TypeString, MAX_TYPES, 2003) types;

#define Min(a, b) ((a) < (b) ? (a) : (b))

int main()
{
    int T, t;

    HashSet_init(types, strhash, strcmp);
    scanf("%d", &T);
    for (t = 0; t < T; t++)
    {
        int i, k, cost;
        int choice[MAX_TYPES];  /* indices to the components chosen */

        /* Read components info. */
        scanf("%d %d", &num_components, &budget);
        HashSet_clear(types);
        for (i = 0; i < num_components; i++)
        {
            char type_str[30], name[30];
            int price, quality, id;
            scanf("%s %s %d %d", type_str, name, &price, &quality);
            HashSet_add(types, type_str, id);
            components[i].price = price;
            components[i].quality = quality;
            components[i].type = id - 1;
        }
        num_types = HashSet_size(types);

        /* Sort the components by quality from lower to higher. */
        qsort(components, num_components, sizeof(component),
              component_quality_comparer);
        
        /* Add a dummy component with highest price and quality. */
        components[num_components].type = -1;
        components[num_components].price = MAX_PRICE + 1;
        components[num_components].quality = MAX_QUALITY + 1;
        components[num_components].upgrade = -1;

        /* Initialize the choice of each type of component to dummy. */
        for (k = 0; k < num_types; k++)
            choice[k] = num_components;

        /* Scan the list of components from high quality to low quality to 
         * build a linked-list of upgrade path for each type of components.
         * For items that are more expensive then their upgrade, we set their
         * attributes equal to their upgrade to effectively remove them from
         * consideration. At the end, we will have a combination of the 
         * cheapest item from each type. This is used as the initial choice.
         */
        for (i = num_components - 1; i >= 0; i--)
        {
            k = components[i].type;
            if (components[i].price >= components[choice[k]].price)
                components[i] = components[choice[k]];
            components[i].upgrade = choice[k];
            choice[k] = i;
        }

        /* Compute the cost of the initial choice. */
        cost = 0;
        for (k = 0; k < num_types; k++)
            cost += components[choice[k]].price;

        /* If the cheapest choice exceeds budget, print an error. */
        if (cost > budget)
        {
            printf("0\n");
            continue;
        }

        /* Improve the quality iteratively by upgrading the lowest-quality
         * component of each type, starting from the component with lowest
         * quality among all types. Repeat until such an upgrade is not 
         * possible either because there are no more available components 
         * of that type or because the total cost would exceed the budget.
         * Since we have put a dummy component at the end of the list, we
         * only need to check the budget condition.
         */
        for (i = 0; i < num_components; i++)
        {
            int next = components[i].upgrade;
            cost += components[next].price - components[i].price;
            if (cost > budget)
                break;
        }

        /* Print the minimum quality of all components, which is the last
         * component which we failed to upgrade.
         */
        printf("%d\n", components[i].quality);
    }
    return 0;
}
